package com.example.algorithm.LinkedListAlgorithm;

/**
 * 算法面试题：快速找到未知长度单链表的中间节点。
 * 你可以普通方法也可用比较好的方法，去解决这个问题。
 * 由于单链表不知道长度，必须遍历完整个单链表才知道单恋表的长度，然后根据一般的长度去找中间结点，这是普通方法。
 * 当然题目问的是快速找到，当然要用快速的方法啦。
 * 这里我们快慢指针的方法来解决这个问题，快指针每次走2个结点，慢指针每次走1个结点，当快指针走完链表，慢指针刚好走到中间，这就是快慢指针的核心思想。
 * @author ZMJ
 * @date 2020/3/23
 */
public class LinkedFindMidNodeByFastSlow {

    public static Node findMidNode(Node head) {
        // 如果为空或只有一个节点,中位节点就是head
        if (head == null || head.getNext() == null) {
            return head;
        }

        // 核心:快指针走完链表的时候,慢指针刚刚指向中间位置;
        Node fast = head;
        Node slow = head;
        while (fast != null && fast.getNext() != null) {
            fast = fast.getNext().getNext();
            slow = slow.getNext();
        }
        return slow;
    }

    public static void main(String[] args) {
        // 构建(偶数)长度链表
        Node head = Node.createLinkedList(10);
        Node.printLinkedList(head);
        Node minNode = findMidNode(head);
        System.out.println("偶数:" + minNode.toString());

        // 构建(奇数)长度链表
        Node head1 = Node.createLinkedList(9);
        Node.printLinkedList(head1);
        Node minNode1 = findMidNode(head1);
        System.out.println("奇数:" + minNode1.toString());
    }

}

